#
# @lc app=leetcode.cn id=5 lang=python3
#
# [5] 最长回文子串
#
# https://leetcode-cn.com/problems/longest-palindromic-substring/description/
#
# algorithms
# Medium (36.33%)
# Likes:    4888
# Dislikes: 0
# Total Accepted:    933.6K
# Total Submissions: 2.6M
# Testcase Example:  '"babad"'
#
# 给你一个字符串 s，找到 s 中最长的回文子串。
# 
# 
# 
# 示例 1：
# 
# 
# 输入：s = "babad"
# 输出："bab"
# 解释："aba" 同样是符合题意的答案。
# 
# 
# 示例 2：
# 
# 
# 输入：s = "cbbd"
# 输出："bb"
# 
# 
# 
# 
# 提示：
# 
# 
# 1 <= s.length <= 1000
# s 仅由数字和英文字母组成
# 
# 
#
# %%
# @lc code=start
class Solution:
    def longestPalindrome(self, s: str) -> str:
        result = ""
        # 中心扩展法
        for i in range(len(s)):
            # 偶数时以i为中心
            even = ""
            l = i; r = i
            # 1、偶数是：s[l:r] is ""；
            # 2、r 右边界是可以等于，字符串的长度的。
            while l >= 0 and r <= len(s) and s[l:r] == s[l:r][::-1]:
                even = s[l:r]
                l -= 1; r+=1
            # 奇数时选定一个字符串
            odd = ""
            l = i; r = i + 1
            # s[l:r] is one character e.g. 'c'
            while l >= 0 and r <= len(s) and s[l:r] == s[l:r][::-1]:
                odd = s[l:r]
                l -= 1; r+=1
            # 3、优雅的max函数应用。
            result = max(even, odd, result, key=len)
        return result


# @lc code=end
